Repunit

In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1. The term stands for repeated unit and was coined in 1966 by Albert H. Beiler. A repunit prime is a repunit that is also a prime number.

1 Definition
2 Properties
3 Factorization of decimal repunits
4 Repunit primes
5 History
6 See also
7 Notes
8 External links
- 8.1 Web sites
- 8.2 Books

Definition

The base-b repunits are defined as

$R_n^{(b)}={b^n-1\over{b-1}}\qquad\mbox{for }b\ge2, n\ge1.$

Thus, the number R_n^(b) consists of n copies of the digit 1 in base b representation. The first two repunits base b for n=1 and n=2 are

$R_1^{(b)}={b-1\over{b-1}}= 1 \qquad \text{and} \qquad R_2^{(b)}={b^2-1\over{b-1}}= b%2B1\qquad\text{for}\ b\ge2.$

In particular, the decimal (base-10) repunits that are often referred to as simply repunits are defined as

$R_n=R_n^{(10)}={10^n-1\over{10-1}}={10^n-1\over9}\qquad\mbox{for }n\ge1.$

Thus, the number R_n = R_n⁽¹⁰⁾ consists of n copies of the digit 1 in base 10 representation. The sequence of repunits base 10 starts with

1, 11, 111, 1111, ... (sequence A002275 in OEIS).

Similarly, the repunits base 2 are defined as

$R_n^{(2)}={2^n-1\over{2-1}}={2^n-1}\qquad\mbox{for }n\ge1.$

Thus, the number R_n⁽²⁾ consists of n copies of the digit 1 in base 2 representation. In fact, the base-2 repunits are the well-respected Mersenne numbers M_n = 2ⁿ − 1.

Properties

Any repunit in any base having a composite number of digits is necessarily composite. Only repunits (in any base) having a prime number of digits might be prime (necessary but not sufficient condition). For example,

R₃₅^(b) = 11111111111111111111111111111111111 = 11111 × 1000010000100001000010000100001 = 1111111 × 10000001000000100000010000001,

since 35 = 7 × 5 = 5 × 7. This repunit factorization does not depend on the base b in which the repunit is expressed.

Any positive multiple of the repunit R_n^(b) contains at least n nonzero digits in base b.

The only known numbers that are repunits with at least 3 digits in more than one base simultaneously are 31 (111 in base 5, 11111 in base 2) and 8191 (111 in base 90, 1111111111111 in base 2). The Goormaghtigh conjecture says there are only these two cases.

It is easy to prove^[1] that given n, such that n is not exactly divisible by 2 or p, there exists a repunit in base 2p that is a multiple of n.

Factorization of decimal repunits

R₁ =	1
R₂ =	11
R₃ =	3 · 37
R₄ =	11 · 101
R₅ =	41 · 271
R₆ =	3 · 7 · 11 · 13 · 37
R₇ =	239 · 4649
R₈ =	11 · 73 · 101 · 137
R₉ =	3 · 3 · 37 · 333667
R₁₀ =	11 · 41 · 271 · 9091

R₁₁ =	21649 · 513239
R₁₂ =	3 · 7 · 11 · 13 · 37 · 101 · 9901
R₁₃ =	53 · 79 · 265371653
R₁₄ =	11 · 239 · 4649 · 909091
R₁₅ =	3 · 31 · 37 · 41 · 271 · 2906161
R₁₆ =	11 · 17 · 73 · 101 · 137 · 5882353
R₁₇ =	2071723 · 5363222357
R₁₈ =	3 · 3 · 7 · 11 · 13 · 19 · 37 · 52579 · 333667
R₁₉ =	1111111111111111111
R₂₀ =	11 · 41 · 101 · 271 · 3541 · 9091 · 27961

Repunit primes

The definition of repunits was motivated by recreational mathematicians looking for prime factors of such numbers.

It is easy to show that if n is divisible by a, then R_n^(b) is divisible by R_a^(b):

$R_n^{(b)}=\frac{1}{b-1}\prod_{d|n}\Phi_d(b)$

where $\Phi_d(x)$ is the $d^\mathrm{th}$ cyclotomic polynomial and d ranges over the divisors of n. For p prime, $\Phi_p(x)=\sum_{i=0}^{p-1}x^i$ , which has the expected form of a repunit when x is substituted with b.

For example, 9 is divisible by 3, and thus R₉ is divisible by R₃—in fact, 111111111 = 111 · 1001001. The corresponding cyclotomic polynomials $\Phi_3(x)$ and $\Phi_9(x)$ are $x^2%2Bx%2B1$ and $x^6%2Bx^3%2B1$ respectively. Thus, for R_n to be prime n must necessarily be prime. But it is not sufficient for n to be prime; for example, R₃ = 111 = 3 · 37 is not prime. Except for this case of R₃, p can only divide R_n for prime n if p = 2kn + 1 for some k.

Decimal repunit primes

R_n is prime for n = 2, 19, 23, 317, 1031,... (sequence A004023 in OEIS). R₄₉₀₈₁ and R₈₆₄₅₃ are probably prime. On April 3, 2007 Harvey Dubner (who also found R₄₉₀₈₁) announced that R₁₀₉₂₉₇ is a probable prime.^[2] He later announced there are no others from R₈₆₄₅₃ to R₂₀₀₀₀₀.^[3] On July 15, 2007 Maksym Voznyy announced R₂₇₀₃₄₃ to be probably prime,^[4] along with his intent to search to 400000. As of September 2010, all further candidates up to R_1300000 have been tested, but no new probable primes have been found so far.

It has been conjectured that there are infinitely many repunit primes^[5] and they seem to occur roughly as often as the prime number theorem would predict: the exponent of the Nth repunit prime is generally around a fixed multiple of the exponent of the (N-1)th.

The prime repunits are a trivial subset of the permutable primes, i.e., primes that remain prime after any permutation of their digits.

Base-2 repunit primes

Main article: Mersenne prime

Base-2 repunit primes are called Mersenne primes.

Base-3 repunit primes

The first few base-3 repunit primes are

13, 1093, 797161, 3754733257489862401973357979128773, 6957596529882152968992225251835887181478451547013, ... (sequence A076481 in OEIS),

corresponding to $n$ of

3, 7, 13, 71, 103, ... (sequence A028491 in OEIS).

Base-4 repunit primes

The only base-4 repunit prime is 5 ( $11_4$ ). $4^n-1=\left(2^n%2B1\right)\left(2^n-1\right)$ , and 3 always divides $2^n%2B1$ when n is odd and $2^n-1$ when n is even. For n greater than 2, both $2^n%2B1$ and $2^n-1$ are greater than 3, so removing the factor of 3 still leaves two factors greater than 1, so the number cannot be prime.

Base 5 repunit primes

The first few base-5 (quinary) repunit primes are

31, 19531, 12207031, 305175781, 177635683940025046467781066894531, (sequence A086122 in OEIS)

corresponding to $n$ of

3, 7, 11, 13, 47, ... (sequence A004061 in OEIS).

Base 6 repunit primes

The first few base-6 repunit primes are

7, 43, 55987, 7369130657357778596659, 3546245297457217493590449191748546458005595187661976371, ..., (sequence A165210 in OEIS)

corresponding to $n$ of

2, 3, 7, 29, 71, ... (sequence A004062 in OEIS)

Base 7 repunit primes

The first few base 7 repunit primes are

2801, 16148168401, 85053461164796801949539541639542805770666392330682673302530819774105141531698707146930307290253537320447270457,
138502212710103408700774381033135503926663324993317631729227790657325163310341833227775945426052637092067324133850503035623601

corresponding to $n$ of

5, 13, 131, 149, ... (sequence A004063 in OEIS)

Base 8 and 9 repunit primes

The only base-8 or base-9 repunit prime is 73 ( $111_8$ ). $8^n-1=\left(4^n%2B2^n%2B1\right)\left(2^n-1\right)$ , and 7 divides $4^n%2B2^n%2B1$ when n is not divisible by 3 and $2^n-1$ when n is a multiple of 3. $9^n-1=\left(3^n%2B1\right)\left(3^n-1\right)$ , and 2 always divides both $3^n%2B1$ and $3^n-1$ .

Base 20 (vigesimal) repunit primes

The only known vigesimal (base 20) repunit primes or probable primes are for $n$ of

3, 11, 17, 1487, 31013, 48859, 61403 ((sequence A127995 in OEIS))

The first three of these in decimal are

421, 10778947368421 and 689852631578947368421

History

Although they were not then known by that name, repunits in base 10 were studied by many mathematicians during the nineteenth century in an effort to work out and predict the cyclic patterns of recurring decimals.^[6]

It was found very early on that for any prime p greater than 5, the period of the decimal expansion of 1/p is equal to the length of the smallest repunit number that is divisible by p. Tables of the period of reciprocal of primes up to 60,000 had been published by 1860 and permitted the factorization by such mathematicians as Reuschle of all repunits up to R₁₆ and many larger ones. By 1880, even R₁₇ had been factored^[7] and it is curious that, though Édouard Lucas showed no prime below three million had period nineteen, there was no attempt to test any repunit for primality until early in the twentieth century. The American mathematician Oscar Hoppe proved R₁₉ to be prime in 1916^[8] and Lehmer and Kraitchik independently found R₂₃ to be prime in 1929.

Further advances in the study of repunits did not occur until the 1960s, when computers allowed many new factors of repunits to be found and the gaps in earlier tables of prime periods corrected. R₃₁₇ was found to be a probable prime circa 1966 and was proved prime eleven years later, when R₁₀₃₁ was shown to be the only further possible prime repunit with fewer than ten thousand digits. It was proven prime in 1986, but searches for further prime repunits in the following decade consistently failed. However, there was a major side-development in the field of generalized repunits, which produced a large number of new primes and probable primes.

Since 1999, four further probably prime repunits have been found, but it is unlikely that any of them will be proven prime in the foreseeable future because of their huge size.

The Cunningham project endeavours to document the integer factorizations of (among other numbers) the repunits to base 2, 3, 5, 6, 7, 10, 11, and 12.

Notes

^ [1]
^ Harvey Dubner, New Repunit R(109297)
^ Harvey Dubner, Repunit search limit
^ Maksym Voznyy, New PRP Repunit R(270343)
^ Chris Caldwell, "The Prime Glossary: repunit" at The Prime Pages.
^ Dickson, Leonard Eugene and Cresse, G.H.; History of the Theory of Numbers; pp. 164-167 ISBN 0-8218-1934-8
^ Dickson and Cresse, pp. 164-167
^ Francis, Richard L.; "Mathematical Haystacks: Another Look at Repunit Numbers" in The College Mathematics Journal, Vol. 19, No. 3. (May, 1988), pp. 240-246.

External links

Web sites

Weisstein, Eric W., "Repunit" from MathWorld.
The main tables of the Cunningham project.
Repunit at The Prime Pages by Chris Caldwell.
Repunits and their prime factors at World!Of Numbers.
Prime generalized repunits of at least 1000 decimal digits by Andy Steward
Repunit Primes Project Giovanni Di Maria's repunit primes page.
The Repunit Primes Project
Factorizations of 11...11 (Repunit) by Makoto Kamada

Books

S. Yates, Repunits and repetends. ISBN 0-9608652-0-9.
A. Beiler, Recreations in the theory of numbers. ISBN 0-486-21096-0. Chapter 11, of course.
Paulo Ribenboim, The New Book Of Prime Number Records. ISBN 0-387-94457-5.

Repunit

Contents

Definition

Properties

Factorization of decimal repunits

Repunit primes

Decimal repunit primes

Base-2 repunit primes

Base-3 repunit primes

Base-4 repunit primes

Base 5 repunit primes

Base 6 repunit primes

Base 7 repunit primes

Base 8 and 9 repunit primes

Base 20 (vigesimal) repunit primes

History

See also

Notes

External links

Web sites

Books